package 旋转数组的最小数字;
//题目描述
//把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
//输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。
//例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。
//NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
public class Solution
{
    public int minNumberInRotateArray(int [] array)
    {
        //前后可以看做两个局部排序的数组，可以使用二分查找法，最小值就是后面数组的首位数，找后数组的第一位数
        //前后两个指针，看两个指针中间的数字，属于哪个数组，如果属于前面的数组，就把中间指针的赋给前面指针，对后面的部分继续二分查找
        //对于三者相等的情况，只能进行顺序查找
        if(array==null||array.length==0)
            return 0;
        //定义指针
        int left=0;
        int right=array.length-1;
        int mid=left;//如果左边的指针小于右面的指针，说明移动了0位，直接返回left
        while (array[left]>=array[right])
        {
            //终止条件
            if (right-left==1)//当左右指针相邻的时候，右指针就是所求
            {
                mid=right;
                break;
            }
            mid=(left+right)/2;
            if (array[left]==array[right]&&array[left]==array[mid])
            {
                //只能顺序查找
                return findInOrder(array,left,right);
            }
            if (array[mid]<=array[right])//所求在mid的前面
                right=mid;
            else if (array[mid]>=array[left])
                left=mid;
        }
        return array[mid];
    }
    public int findInOrder(int[] array,int left,int right)
    {
        int res=0;
        for (int i = left; i <= right; i++)
        {
            if (res>array[i])
                res=array[i];
        }
        return res;
    }

}
